package com.xy6.algo.force;

import java.util.Arrays;

/**
 * 蛮力法求解分配问题
 * <pre>
 * 设有n件工作分配给n个人。为第i个人分配工作j所需的费用为c[i][j]。
 * 试设计一个算法，计算最佳工作分配方案，为每一个人都分配1件不同的工作，并使总费用达到最小。
 * 
 * 时间复杂度：O(n!)
 * </pre>
 * 
 * @author zhang
 * @since 2017-12-30
 */
public class Arrange {

	public static void main(String[] args){
		int personNum = 3;
		int[][] cost = { { 10, 15, 20 }, { 16, 17, 18 }, { 25, 20, 15 } };
		
		Arrange range = new Arrange();
		System.out.println(range.calc(personNum, cost));
	}
	
	/**
	 * 全排列个数记录
	 */
	private int count = 0;
	
	/**
	 * 蛮力法求解分配问题，计算最小费用
	 * 
	 * @param personNum
	 * @param cost
	 * @return
	 */
	public int calc(int num, int[][] cost){
		// 人员编号集合
		int[] full = new int[num];
		for (int i = 0; i < num; i++) {
			full[i] = i;
		}
		int[] arr = new int[full.length];
		// 计算全排列总数
		int rangeNum = calc(full.length);
		int[][] fullRange = new int[rangeNum][];
		
		this.fullSort(full, arr, 0, fullRange);
		
		int min = -1;
		int temp;
		// 每个任务对应的人员编号序列
		int[] tempArr = new int[num];
		for (int i = 0; i < fullRange.length; i++) {
//			System.out.println(Arrays.toString(fullRange[i]));
			temp = calcCost(fullRange[i], cost);
			if(min == -1 || temp < min){
				min = temp;
				tempArr = fullRange[i];
			}
		}
		System.out.println(Arrays.toString(tempArr));
		
		return min;
	}
	
	/**
	 * 递归输出全排列各序列，将序列保存到一个集合中
	 * 
	 * @param full
	 * @param arr
	 * @param idx
	 * @param count
	 * @param fullRange
	 */
	private void fullSort(int[] full, int[] arr, int idx, int[][] fullRange){
		if(idx >= full.length){
			return;
		}
		for(int i=0; i<full.length; i++){
			boolean exist = false;
			for (int j = 0; j < idx; j++) {
				if(full[i] == arr[j]){
					exist = true;
					break;
				}
			}
			if(exist){
				continue;
			}
			arr[idx] = full[i];
			if(idx == full.length - 1){
				// 逐个复制元素，避免引用传递
				fullRange[count] = new int[arr.length];
				for (int k = 0; k < arr.length; k++) {
					fullRange[count][k] = arr[k];
				}
				count++;
			}
			fullSort(full, arr, idx + 1, fullRange);
		}
	}
	
	/**
	 * 计算n的阶乘
	 * 
	 * @param n
	 * @return
	 */
	private static int calc(int n){
		int total = 1;
		for(int i=1; i<=n; i++){
			total = total * i;
		}
		return total;
	}
	
	/**
	 * 把某项任务分配给某个人时，计算总费用
	 * 
	 * @param persons
	 * @param cost
	 * @return
	 */
	private static int calcCost(int[] persons, int[][] cost){
		int total = 0;
		int count = 0;
		for (int i = 0; i < persons.length; i++) {
			total += cost[persons[i]][count++];
		}
		
		return total;
	}
	
}
